Every ATM connection is distinguished by VPI/VCI in an ATM network. With faster and faster transmitting speed, the receivers of ATM network, limited by only 53 bytes of each cell, has to complete each VPI/VCI recognition and processing in a very short period of time. At the receiver of a network interface card, cells should be successfully transferred to the top layer; and for the input port of switch, the next output port and new VPI/VCI value should be found as soon as possible.
At the User-Network Interface (UNI), VPI and VCI takes 8 and 16 bits respectively. 12 and 16 bits are occupied at the Network-Network Interface (NNI). A total of 24 bits are used by UNI, and 28 bits are used by NNI. If the same size as the above-said total bits is directly used in the index table, 224 (UNI) or 228 (NNI) entries are needed for the Table. It means an extremely high cost in hardware, although related data can be directly indexed.
As a general, the VPI/VCI connection amount of each input port of ATM network will not exceed 224 or 228. Thus, there are usually two ways adopted by the receivers to recognize VPI/VCI connections. One is done by an Application Specific Integrated Circuit (ASIC) via the hashing method applied in computer science, the hardware used is more complicated, and the other uses Content Addressable Memory (CAM), which costs a lot in hardware. These two methods are not covered in the invention.
The primary purpose of the invention is to study the theory of the indexing function, as shown in FIG. 1, illustration of VPI/VCI indexing applied at the ATM receivers. The VPI/VCI, used as input and calculated via an indexing function, produces an index value of n bits. Since the word of every data entry is W, the corresponding offset to the index table is obtained by n multiplied with W. According to the obtained offset value, adding up the base pointer for storing exact indexed data, corresponding indexed data entry can be found. Two usual and simple ways for application of the indexing function as shown in FIG. 1 are truncation and exclusive-OR.
Before looking into the truncation and exclusive-OR methods, we have to make clear that the methods for selection VPI/VCI for switches are as follows. First, the ceiling and bottom VCI values of an ATM are set and the VPI value is determined by the users as required; second, variable Least Significant Bits (LSB) for VPI and VCI are set.
The bits taken by VPI and VCI may be adjusted via an network interface card designed for ATMs using the truncation method, and may also be applied directly to the index in order to avoid obtaining the same index value through different VPI/VCI values, such a phenomenon is called collision. If an ATM, equipped with this kind of network card, both the switch and network interface card must be set to determine which bits will be used for indexing. However, the invention hereby presents a reverse compensation indexing method, and thus only the setting of switches has to be done. Here we would like to show the defects of the exclusive-OR method by the example below:
The following formula is used as an indexing value for those with 0·12 indexing bits in the exclusive-OR method:({VPI[7:0], VCI[15:12]}⊕VCI[11:0]) & (2TAB—SIZE−1) which ⊕ represents the exclusive-OR of each bit, & represents the AND operation of each bit, and TAB_SIZE, an abbreviation of Table Size, represents the bit width of an index value.
To illustrate the inapplicable occasions of the exclusive-OR method, the following example is given:
If TAB_SIZE=7, the exclusive-OR indexing formula is                     (                              {                                          VPI                ⁡                                  [                                      7                    :                    0                                    ]                                            ,                              VCI                ⁡                                  [                                      15                    :                    12                                    ]                                                      }                    ⊕                      VCI            ⁡                          [              11.0              ]                                      )            &        ⁢          (                        2          TAB_SIZE                -        1            )        ⁢          =                              (                                    {                                                VPI                  ⁡                                      [                                          7                      :                      0                                        ]                                                  ,                                  VCI                  ⁡                                      [                                          15                      :                      12                                        ]                                                              }                        ⊕                          VCI              ⁡                              [                                  11                  :                  0                                ]                                              )                &            ⁢              (                              2            7                    -          1                )              ⁢                  =                                        (                                          {                                                      VPI                    ⁡                                          [                                              7                        :                        0                                            ]                                                        ,                                      VCI                    ⁡                                          [                                              15                        :                        12                                            ]                                                                      }                            ⊕                              VCI                ⁡                                  [                                      11                    :                    0                                    ]                                                      )                    &                ⁢                              (            1111111            )                    2                    ⁢                          =              (                              {                                          VPI                ⁡                                  [                                      2                    :                    0                                    ]                                            ,                              VCI                ⁡                                  [                                      15                    :                    12                                    ]                                                      }                    ⊕                      VCI            ⁡                          [                              6                :                0                            ]                                      )            
If ranges used by current VPI/VCI in ATM switches are:min(VPI)=0,max(VPI)=0,min(VCI)=0,max(VCI)=127=(1111111)2then no collision of index values will occur. But as in the condition below:min(VPI)=0,max(VPI)=1,min(VCI)=0,max(VCI)=63=(111111)2would result in at least one occasion that produces collisions:(VPI/VCI)=( 0/16), wherein the formula is:             {                        VPI          ⁡                      [                          2              :              0                        ]                          ,                  VCI          ⁡                      [                          15              :              12                        ]                              }        ⊕          VCI      ⁡              [                  6          :          0                ]              ⁢          =                              (          0010000          )                2            ⊕                        (          0000000          )                2              ⁢                  =                  (        0010000        )            2      
For another occasion that produces collisions: (VPI/VCI)=( 1/0) the formula is:             {                        VPI          ⁡                      [                          2              :              0                        ]                          ,                  VCI          ⁡                      [                          15              :              12                        ]                              }        ⊕          VCI      ⁡              [                  6          :          0                ]              ⁢          =                              (          0010000          )                2            ⊕                        (          0000000          )                2              ⁢                  =                  (        0010000        )            2      
Apparently, at least one collision exists that both ( 0/16) and ( 1/0) index the same value.
In other words, if there is only one VPI in coordination with the above-said ATM switch without the exclusive-OR concept of the invention, it can only achieve at most the effect of “collision free” equivalent to the indexing bit width. Furthermore, if there are more than one VPI numbered in series, collisions will occur, because bit 0 of VPI (VPI[0]) are exclusive with variable bits of VCI (e.g. VCI [4] as said in the above example). Therefore, selection of suitable VPI number group can avoid occurrence of collisions, but the load of switch settings is increasing accordingly. This method of VPI number selection fits to the ATM switches using the first setting method said above, but for those using the second method, via setting of some lower Least Significant Bit (LSB), they are apparently not applicable with network interface cards with exclusive-OR functions.
To improve current ATM network's operating conditions, especially on prevention of collisions, an indexing method that corresponds the multi-sectional encoding structures to a single indexing table is proven in the next section of the invention. This indexing method can also be applied to the reverse compensation indexing method for VPI/VCI of multi-sectional encoding structures in ATM networks. We will illustrate the way that this flexible reverse compensation indexing method improves present conditions. Here in below, max stands for maximum, meaning a ceiling limit or the maximum value, and min stands for minimum, meaning a bottom limit or the minimum value. The remarkable feature of the Reverse Compensation Indexing Method is that if min(VPI)=0 and min(VCI)=0 and a same circuit can be used in:                                                                         max                ⁢                                                                   ⁢                                  (                  VPI                  )                                            =                                                2                                      k                    0                                                  -                1                                                                                                                          max                  ⁢                                                                           ⁢                                      (                    VCI                    )                                                  =                                                      2                                          n                      -                                              k                        0                                                                              -                  1                                            ,                                          ⁢                           ⁢              k        0              =    0    ,  1  ,  ...           ,           ⁢  nup to (n+1) occasions, all of which have the effect of “collision free.” FIG 1. illustrates an executable VPI/VCI indexing method for ATM input terminals. The whole indexing method can be divided into three stages: operation of index values, production of addresses, and accessing of memory. If the time for operation of index values made as ti, time for production of addresses as ta, and time for accessing of memory is tm, then the circuit for the Reverse Compensation Indexing Method applied in the entire indexing system can support a speed of processing 1/(ti+ta+tm) ATM cells per second. If the time of exclusive-OR gate delay is tx(by second), then t1=tx.